Фундована множина

Фундована множина (фундований порядок) — частково впорядкована множина, в якій для кожної непорожньої підмножини існує мінімальний елемент. Мінімальних елементів може бути декілька і навіть нескінченна кількість. Формально, якщо на множині (або класі) $X$ задане бінарне відношення $R$ і для кожної $S\subseteq X$ існує мінімальний щодо $R$ елемент $m,$ для якого не існує елемента $s$ такого, що виконується $sRm.$ Тобто,

(\forall S\subseteq X)\;[S\neq \emptyset \implies (\exists m\in S)(\forall s\in S)\lnot (sRm)].

Інакше можна сказати, що множина фундована тоді і тільки тоді, коли в ній не існує нескінченної спадної послідовності елементів.

Приклади

Фундовані, але не лінійно впорядковані множини:

додатні цілі числа {1, 2, 3, ...}, з порядком визначеним як a < b тоді і тільки тоді, коли a ділить b і a ≠ b.
множина всіх скінченних рядків над фіксованою абеткою з порядком визначеним як s < t тоді і тільки тоді, якщо s це власний підрядок t.
множина N × N двійок натуральних чисел, впорядкованих так: (n₁, n₂) < (m₁, m₂) тоді і тільки тоді, якщо n₁ < m₁ і n₂ < m₂.
множина всіх регулярних виразів над фіксованою абеткою з порядком визначеним як s < t тоді і тільки тоді, якщо s це власний (правильний) підвираз t.
будь-який клас чиї елементи це множини з відношенням $\in$ ("елемент з"). Це аксіома регулярності.
вузли будь-якого скінченного скінченного ациклічного графу, з відношенням R визначеним так: a R b тоді і тільки тоді, якщо існує ребро від a до b.

Приклади нефундованих відношень включають:

від'ємні цілі числа {−1, −2, −3, …}, зі стандартним порядком, бо будь-яка необмежена множина не має найменшого елемента.
Множина рядків над скінченною абеткою з більш ніж одним елементом, зі звичайним (лексикографічним) порядком, бо послідовність "B" > "AB" > "AAB" > "AAAB" > … це нескінченний спадний ланцюг. Це відношення не фундоване навіть незважаючи на те, що вся множина має мінімільний елемент, а саме порожній рядок.
раціональні числа (або дійсні) зі стандартним порядком, бо, наприклад, множина додатних раціональних (або дійсних) не має мінімуму.